Search results for "Counting problem"

showing 3 items of 3 documents

On a Conjecture by Christian Choffrut

2017

It is one of the most famous open problems to determine the minimum amount of states required by a deterministic finite automaton to distinguish a pair of strings, which was stated by Christian Choffrut more than thirty years ago. We investigate the same question for different automata models and we obtain new upper and lower bounds for some of them including alternating, ultrametric, quantum, and affine finite automata.

Discrete mathematicsFinite-state machineConjecture010102 general mathematics02 engineering and technology01 natural sciencesUpper and lower boundsAutomatonDeterministic finite automatonCounting problem0202 electrical engineering electronic engineering information engineeringComputer Science (miscellaneous)020201 artificial intelligence & image processingAffine transformation0101 mathematicsUltrametric spaceMathematicsInternational Journal of Foundations of Computer Science
researchProduct

Computing the Probability for Data Loss in Two-Dimensional Parity RAIDs

2017

Parity RAIDs are used to protect storage systems against disk failures. The idea is to add redundancy to the system by storing the parity of subsets of disks on extra parity disks. A simple two-dimensional scheme is the one in which the data disks are arranged in a rectangular grid, and every row and column is extended by one disk which stores the parity of it.In this paper we describe several two-dimensional parity RAIDs and analyse, for each of them, the probability for dataloss given that f random disks fail. This probability can be used to determine the overall probability using the model of Hafner and Rao. We reduce subsets of the forest counting problem to the different cases and show…

Discrete mathematicsHardware_MEMORYSTRUCTURESRAIDComputer science020206 networking & telecommunications02 engineering and technologyData lossGridElectronic mail020202 computer hardware & architecturelaw.inventionExact algorithmCounting problemlawData_FILES0202 electrical engineering electronic engineering information engineeringTutte polynomialParity (mathematics)2017 13th European Dependable Computing Conference (EDCC)
researchProduct

Advanced Scatter Search for the Max-Cut Problem

2009

The max-cut problem consists of finding a partition of the nodes of a weighted graph into two subsets such that the sum of the weights on the arcs connecting the two subsets is maximized. This is an NP-hard problem that can also be formulated as an integer quadratic program. Several solution methods have been developed since the 1970s and applied to a variety of fields, particularly in engineering and layout design. We propose a heuristic method based on the scatter-search methodology for finding approximate solutions to this optimization problem. Our solution procedure incorporates some innovative features within the scatter-search framework: (1) the solution of the maximum diversity prob…

Mathematical optimizationOptimization problemCounting problemCutting stock problemMaximum cutGeneral EngineeringP versus NP problemPartition problemComputational problemMetaheuristicMathematicsINFORMS Journal on Computing
researchProduct